﻿using System.Collections.Generic;
using System.Text;
using UnityEngine;

namespace DL.SearchAlgorithm
{
    // 深度优先搜索，存放了所有可达路径
    public class Dfs
    {
        /// <summary>
        /// 搜索方向 
        /// </summary>
        private DfsPos[] _direct = new DfsPos[4]
        {
            new DfsPos(0, -1), new DfsPos(1, 0), new DfsPos(0, 1), new DfsPos(-1, 0),
        };

        private int[][] _gameMap;
        private int _row;
        private int _col;
        private bool[][] _vis;
        private DfsPos _startPos;
        private DfsPos _endPos;

        private List<DfsPos> _path = new();
        private List<DfsPos[]> _pathVec = new();

        
        /// <summary>
        /// 初始化
        /// </summary>
        /// <param name="map"></param>
        /// <param name="row"></param>
        /// <param name="col"></param>
        /// <param name="startPos"></param>
        /// <param name="endPos"></param>
        public void Init(int[][] map, int row, int col, DfsPos startPos, DfsPos endPos)
        {
            _gameMap = map;
            _row = row;
            _col = col;
            _path.Clear();
            _pathVec.Clear();

            _startPos = startPos;
            _endPos = endPos;

            _vis = new bool[_row][];
            for (int i = 0; i < _vis.Length; i++)
            {
                bool[] vis;
                vis = new bool[col];
                for (int j = 0; j < vis.Length; j++)
                {
                    vis[j] = false;
                }
                _vis[i] = vis;
            }
        }

        public void DfsSearchStart()
        {
            DfsSearch(_startPos);
        }

        public void DfsSearch(DfsPos pos)
        {
            //找到一条路 
            if (pos == _endPos)
            {
                _pathVec.Add(_path.ToArray());
                Debug.Log("找到一条路径");
                return;
            }
            
            //标记已访问
            _vis[pos.PosX][pos.PosY] = true;
            _path.Add(pos);

            for (int i = 0; i < _direct.Length; i++)
            {
                DfsPos newPos = pos + _direct[i];
                //判断越界 && 未访问 && 可以走  
                if (In(newPos) && !_vis[newPos.PosX][newPos.PosY] && _gameMap[newPos.PosX][newPos.PosY] == 0)
                {
                    DfsSearch(newPos);
                }
            }
            
            //回溯  
            _vis[pos.PosX][pos.PosY] = false;
            _path.RemoveAt(_path.Count - 1);
        }
        
        //打印每条路径
        public void DisplayAllPath()
        {
            Debug.Log("路径条数： " + _pathVec.Count);
            StringBuilder sb = new StringBuilder();
            foreach (var path in _pathVec)
            {
                sb.AppendJoin("-->", path);
                sb.AppendLine();
            }
            Debug.Log(sb.ToString());
        }

        /// <summary>
        /// 判断越界
        /// </summary>
        /// <param name="pos"></param>
        /// <returns></returns>
        bool In(DfsPos pos)
        {
            return pos.PosX >= 0 && pos.PosX < _row && pos.PosY >= 0 && pos.PosY < _col;
        }
    }
}